package com.liuyubo.sort;

import java.util.Arrays;

public class ShellSort implements Sort {

    @Override
    public void sort(int[] arr) {
        shellSort(arr, arr.length);
    }

    void shellSort(int[] arr, int n){

        int h = 1;
        while( h < n/3 ) {
            h = 3 * h + 1;
        }
        // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...

        while( h >= 1 ){
            // h-sort the array
            for( int i = h ; i < n ; i ++ ){

                // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
                int e = arr[i];
                int j;
                for( j = i ; j >= h && e < arr[j-h] ; j -= h ) {
                    arr[j] = arr[j - h];
                }
                arr[j] = e;
            }
            h /= 3;
        }
    }

    @Override
    public String getName() {
        return "Shell Sort";
    }

    public static void main(String[] args) {
        int[] arr = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        ShellSort sort = new ShellSort();
        sort.sort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }
}
